package geek;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

public class Graph_algorithm_day1 {
	
	/**
	 * Graph Traversal: start from one node, and visit all other nodes
	 *                  all nodes must be visited only once
	 */
	
	
	/**
	 * For DFS & adjacency list, the complexity would be O(n+2m)
	 * for matrix, it would be O(n^2)
	 * @param adjacencyList
	 * @param start
	 */
	public static void dfsIterately(List<Integer>[] adjacencyList, int start){
		Stack<Integer> s = new Stack<Integer>();
		s.push(start);
		boolean[] visited = new boolean[adjacencyList.length];
		visited[0] = true;
		while(!s.isEmpty()){
			int cur = s.pop();
			//if(!visited[cur]){//should add this or we will arrive the same node many times
				              //if there are many edges connect to it
				visited[cur] = true;
				System.out.println(cur);
				//when visiting this node, we can do something here
				for(int i = adjacencyList[cur].size()-1 ; i >= 0 ; i--){
					if(!visited[adjacencyList[cur].get(i)]){
						visited[adjacencyList[cur].get(i)] = true;
						s.push(adjacencyList[cur].get(i));
					}
				}
				//here we can reset the node to be not visited
				//then we can visit all paths
				//visited[cur] = false;
				//however, if the graph contains circle, if there is no
				//other termination condition, it will lead to infinite loop
			//}
		}
	}
	
	
	public static void dfsRecursionly(List<Integer>[] adjacencyList, int cur, boolean[] visited){
		//if(!visited[cur]){
			visited[cur] = true;
			System.out.println(cur);
			for(int node : adjacencyList[cur]){
				if(!visited[node]) dfsRecursionly(adjacencyList, node, visited);
			}
		//}
	}
	
	
	/**
	 * It has been extremely useful if all of the edges in a graph are unweight 
	 * (or same weight) then the first time a node is visited is the shortest 
	 * path to that node from the source node.
	 * 
	 * It always associates with optimal answer to one question.
	 * @param adjacencyList
	 * @param start
	 */
	public static void bfs(List<Integer>[] adjacencyList, int start){
		Queue<Integer> q = new LinkedList<Integer>();
		boolean[] visited = new boolean[adjacencyList.length];
		q.offer(start);
		visited[0] = true;
		
		while(!q.isEmpty()){
			int cur = q.poll();
			//if(!visited[cur]){
				//visited[cur] = true;
				System.out.println(cur);
				for(int i : adjacencyList[cur])
					if(!visited[i]) {
						visited[i] = true;
						q.offer(i);
					}
			//}
		}
	}
	
	/**
	 * Dijkstra Algorithm:
	 * 	Single source, find the shortest paths for all other nodes
	 * 	The weight on the edges should be non-negative
	 * 
	 * 1. Maintain set S of vertices where shortest path distance from source is known.
	 * 2. At each step, add to S the vertex v in V - S where distance from S is minimum.
	 * 3. Update distance estimates of vertices adjacent to v.
	 * @param adja
	 * @param start
	 */
	public static void dijkstra(double[][] adjMatrix, int start){
		HashMap<Integer, Double> distance = new HashMap<Integer, Double>();//set s
		distance.put(start, 0.0);
		
		PriorityQueue<Edge> q = new PriorityQueue<Edge>(adjMatrix.length * 2, new Comparator<Edge>(){

			@Override
			public int compare(Edge o1, Edge o2) {
				if(o1.weight > o2.weight) return 1;
				else if(o1.weight < o2.weight) return -1;
				return 0;
			}
			
		});
		
		while(distance.size() != adjMatrix.length){
			//find the nearest vertex outside set S
			q.clear();
			for(Integer k : distance.keySet()){
				for(int i = 0 ; i < adjMatrix.length ; i++)
					if(!distance.keySet().contains(i))
						q.add(new Edge(k, i, adjMatrix[k][i]));
				Edge e = q.peek();
				distance.put(e.v, distance.get(e.u)+e.weight);
				//update all vertices in S adjacent to v
				for(int i = 0 ; i < adjMatrix.length ; i++){
					if(distance.keySet().contains(i))
						distance.put(i, Math.min(distance.get(i), distance.get(e.v)+adjMatrix[e.v][i]));
				}
			}
		}
		
		System.out.println();
		for(Integer i : distance.keySet())
			System.out.println("Distance from "+start+" to "+i+"is: "+distance.get(i));
		System.out.println();
	}
	/**
	 * visit all vertices once and copy their neighbors.
	 * @param n
	 * @param map
	 * @return
	 */
	public static Node cloneGraphRecursivelyDFS(Node n, HashMap<Node, Node> map){
		if(n == null) return n;
		Node nCopy = null;
		if(!map.containsKey(n)) {//visit n
			nCopy = new Node();
			for(Node nei : n.neighbors){
				nCopy.neighbors.add(cloneGraphRecursivelyDFS(nei, map));
			}
			map.put(n, nCopy);
		}
		else nCopy = map.get(n);

		return nCopy;			
	}
	/**
	 * Ensure every node has a copy in map before putting them in queue
	 * And we only put the node which doens't have a copy previously.
	 * 
	 * After popping a node from the queue, we add the neighbors to it's copy
	 * 
	 * @param n
	 * @return
	 */
	public static Node cloneGraphBFS(Node n){
		if(n == null) return null;
		Queue<Node> q = new LinkedList<Node>();
		q.offer(n);
		Node nCopy = new Node();
		HashMap<Node, Node> map = new HashMap<Node, Node>();
		map.put(n, nCopy);
		
		while(!q.isEmpty()){
			Node cur = q.poll();//visit cur
			for(Node nei : cur.neighbors){//add neighbors to cur
				if(!map.containsKey(nei)){
					Node neiCopy = new Node();
					Node curCopy = map.get(cur);
					if(curCopy.neighbors == null) curCopy.neighbors = new ArrayList<Node>();
					curCopy.neighbors.add(neiCopy);
					map.put(nei, neiCopy);
					q.offer(nei);
				}else map.get(cur).neighbors.add(map.get(nei));
			}
		}
		
		return nCopy;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node n = new Node();
		n.neighbors = new ArrayList<Node>();
		Node n1 = new Node();
		n1.neighbors = new ArrayList<Node>();
		Node n2 = new Node();
		n2.neighbors = new ArrayList<Node>();
		
		n.neighbors.add(n1); n1.neighbors.add(n);
		n2.neighbors.add(n);n.neighbors.add(n2);
		
		Node res = cloneGraphBFS(n);
		
		
		List<Integer>[] adja = new ArrayList[9];
		for(int i = 0 ; i < 9 ; i++)
			adja[i] = new ArrayList<Integer>();
		adja[0].add(1); adja[0].add(4); adja[0].add(6);
		adja[1].add(0); adja[1].add(2); adja[1].add(4);
		adja[2].add(1); adja[2].add(3);
		adja[3].add(2); 
		adja[4].add(0); adja[4].add(1); adja[4].add(5);
		adja[5].add(4); adja[5].add(6); adja[5].add(7);
		adja[6].add(0); adja[6].add(5);
		adja[7].add(5); adja[7].add(8);
		adja[8].add(7);
		
		dfsIterately(adja,0);
		System.out.println("**********");
		dfsRecursionly(adja, 0, new boolean[adja.length]);
		System.out.println("**********");
		bfs(adja, 0);
	}

}

class Node{
	List<Node> neighbors = new ArrayList<Node>();
}

class Edge{
	public int u = -1;
	public int v = -1;
	public double weight = 0.0;
	
	public Edge(int u, int v, double w){
		this.u = u;
		this.v = v;
		this.weight = w;
	}
}
